// 前缀树Trie
class TrieNode
{
public:
    unordered_map<char, TrieNode*> children;
    string isWord;

    TrieNode()
        : isWord("")
    {}

    void insert(const string &word)
    {
        int n = word.size();
        TrieNode *cur = this;
        for(int i = 0; i < n; i++)
        {
            if(cur->children.count(word[i]) == 0)
                cur->children[word[i]] = new TrieNode();
            cur = cur->children[word[i]];
        }
        cur->isWord = word;
    }
};


class Solution {
    set<string> path;
    int m, n;
    void dfs(vector<vector<char>>& board, int x, int y, TrieNode *node)
    {
        if((x < 0 || x >= m || y < 0 || y >= n) || board[x][y] == '*' || !node->children.count(board[x][y]))
            return;
        
        node = node->children[board[x][y]];
        if(node->isWord != "" && !path.count(node->isWord))
            path.insert(node->isWord);
        
        // 标记为已访问节点
        char ch = board[x][y];
        board[x][y] = '*';
        dfs(board, x, y - 1, node);
        dfs(board, x, y + 1, node);
        dfs(board, x + 1, y, node);
        dfs(board, x - 1, y, node);
        board[x][y] = ch;   // 恢复现场(回溯)
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        m = board.size();
        n = board[0].size();
        TrieNode *root = new TrieNode();
        vector<string> ret;

        // 将单词列表插入前缀树
        for(auto &word : words)
            root->insert(word);

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                dfs(board, i, j, root);


        for(auto &word : path)
            ret.push_back(word);
        return ret;
    }
};